1. Field of the Invention
The present invention relates in general to computers, and more particularly to methods, computer systems, and computer program products for parallel computation of a remainder by division of a sequence of bytes.
2. Description of the Related Art
The Rabin-Karp hash is used extensively in string matching algorithms, in part because it is a rolling hash. That is, an initial (or base) hash is calculated for a window (or seed) of bytes that is a part of a larger segment of data. Then the window is shifted down one byte (i.e. one byte from the segment leaves the window and another enters). Then the hash of the bytes in the window at its new position is calculated.
Calculating the initial hash of the window at the start of the segment requires considerable processing power. In particular, it requires O(n) operations, where n is the size of the window.
However, recalculating the hash after the window shifts is a much less exhaustive process and requires only the following operations: a figurative subtraction to compensate for the byte leaving the window, a shift and normalization to account for the bytes in the window shifting their positions, a figurative addition to account for the byte entering the window, and calculating a remainder of the division of the result so far by a given number P.